package com.zhupf.Backtracking;

/**
 * @author zhupf
 * @date 2023年12月27日 10:49
 * @Description
 *
 * 79. 单词搜索
 */
public class Exist {

    private static boolean ans = false;

    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        exist(board,"ABCB");
    }

    public static boolean exist(char[][] board, String word) {
        int[][] revisited = new int[board.length][board[0].length];
        for (int i = 0; i < board.length && !ans; i++) {
            for (int j = 0; j < board[i].length && !ans; j++) {
                dfs(0,board,word,i,j,revisited);
            }
        }
        return ans;
    }

    private static void dfs(int idx,char[][] board,String word,int x,int y,int[][] revisited){
        if(revisited[x][y] == 1 || idx>=word.length() || board[x][y] != word.charAt(idx)  ){
            return;
        }
        revisited[x][y] = 1;
        if(idx == word.length()-1){
            ans = true;
            return ;
        }
        idx++;
        if(x>0){
            dfs(idx,board,word,x-1,y,revisited);
        }
        if(x<board.length-1){
            dfs(idx,board,word,x+1,y,revisited);
        }
        if(y>0){
            dfs(idx,board,word,x,y-1,revisited);
        }
        if(y<board[0].length-1){
            dfs(idx,board,word,x,y+1,revisited);
        }
        revisited[x][y] = 0;
    }
}
